#include <stdio.h>
#include <string.h>
#include <iostream>


//排除因scanf溢出警告
#pragma warning(disable:6031) 
#pragma warning(disable:4996) 

#define LIST_INIT_SIZE 80 // 线性表存储空间的初始分配量
#define LISTINCREMENT 10 // 线性表存储空间的分配增量
 
using namespace std;
 
typedef int Status;
typedef int ElemType;
 
//创建顺序表
typedef struct{
    int *Elem;// 存储空间基址，使用相当于数组
    int Length;// 当前长度
    int ListSize;// 当前分配的存储容量
}Sqlist;
 
//采用冒泡排序对线性表进行排列
void Sort(Sqlist &L)
{
	int n=L.Length;
    for(int i=n;i>=0;i--){
        for(int j=i-1;j>=0;j--){
            if(L.Elem[i]>L.Elem[j]){ //每次进行对比
                int t=L.Elem[i];
                L.Elem[i]=L.Elem[j];
                L.Elem[j]=t;
            }
        }
    }
}

//Init_List
Status Init_List(Sqlist &L)
{
	L.Elem = new ElemType[LIST_INIT_SIZE];
	if(!L.Elem) exit(0);
	L.Length = 0;
	return 1;
}

//Initlist
Status InitList(Sqlist &L)
{
    L.Elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));//动态分配空间 原义：把L的Elem指向的那段内存扩大
    if(!L.Elem) exit(-1); //空间分配不成功，退出
    L.Length=0;//顺序表当前长度为0
    L.ListSize=LIST_INIT_SIZE;// 当前分配的存储容量，相当于数组的大小
    return 1;
}

//ListInsert
Status ListInsert(Sqlist &L,int i,int e)
{
    if(i<1||i>L.Length) return 0;//判断插入位置是否合法
    if (L.Length >= L.ListSize){ // 当前存储空间已满，增加分配
        int *newbase = (ElemType *)realloc(L.Elem,(L.ListSize+LISTINCREMENT)*sizeof (ElemType));
        if (!newbase) exit(-1);//存储分配失败
        L.Elem = newbase;// 新基址
        L.ListSize += LISTINCREMENT; //增加存储容量
    }
    int *q,*p;
    q=&(L.Elem[i-1]);//指针q表示插入位置
    for(p=&(L.Elem[L.Length-1]);p>=q;p--){
        *(p+1)=*p;//插入位置及之后的元素右移
    }
    *q=e;//插入元素e
    L.Length++;//顺序表长度加1
    return 1;
}

//删除i位置上的元素
Status ListIndele(Sqlist &L,int i,int &e)
{
    if(i<1||i>L.Length) return 0;//判断删除位置是否合法
    int *p,*q;
    e=L.Elem[i-1];//记录被删除元素的值
    q=&(L.Elem[L.Length-1]);
    for(p=&(L.Elem[i-1]);p<q;p++)
        *p=*(p+1);//将值左移
    L.Length--;//顺序表长度减1
    return 1;
}

//输入链表函数
Status ListInprint(Sqlist &L)
{
   //判断是否合法
	while(true){
		printf("请输入顺序表长度：");
		scanf("%d",&L.Length);
		if (L.Length>0) break;
	}
	printf("\n请输入%d个元素：",L.Length);
	for(int i=0;i<L.Length;i++){
        scanf("%d",&L.Elem[i]);
    }
	return 0;
}



//合并顺序表
void MergeList(Sqlist La,Sqlist Lb,Sqlist &Lc)
{
    int *Pa,*Pb,*Pc;
    int *Pa_Last,*Pb_Last;
    Pa=La.Elem;Pb=Lb.Elem;
    Lc.ListSize=Lc.Length=La.Length+Lb.Length;//Lc的长度
    Pc=Lc.Elem=(ElemType *)malloc(Lc.ListSize*sizeof(ElemType));//给Lc动态分配空间
    if(!Lc.Elem)  exit(-1); //分配空间
    Pa_Last=La.Elem+La.Length-1;//记录La的最后元素存放位置
    Pb_Last=Lb.Elem+Lb.Length-1;//记录Lb的最后元素存放位置
    while(Pa<=Pa_Last&&Pb<=Pb_Last){//归并操作
        if(*Pa<=*Pb)
            *Pc++=*Pa++;
        else
            *Pc++=*Pb++;
    }
    while (Pa<=Pa_Last) *Pc++=*Pa++;//若 La 不空
    while (Pb<=Pb_Last) *Pc++=*Pb++;//若 Lb 不空

}

int main()
{
    Sqlist La,Lb,Lc;
    InitList(La);//初始化La
    InitList(Lb);//初始化Lb
    printf("******请输入La顺序表*********\n\n");
    ListInprint(La);
    printf("******请输入Lb顺序表*********\n\n");
    ListInprint(Lb);
            while(1){
            	system("cls");
				
                MergeList(La,Lb,Lc);//合并

				printf("\n合并之后的顺序表为：\n");
			    for(int i=0;i<Lc.Length;i++){
			        printf("%d ",Lc.Elem[i]);
			    }
			    printf("\n");

				Sort(Lc);//排序
				
				//Converse(Lc);
                printf("\n排序之后的顺序表为：\n");
			    for(int i=0;i<Lc.Length;i++){
			        printf("%d ",Lc.Elem[i]);
			    }
			    printf("\n");
				system("pause");
                //return 0;
           }
    return 0;
}